This tag is for basic questions about the study of finite or countable discrete structures — specifically how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions. ...

learn more… | top users | synonyms (4)

2
votes
3answers
642 views

Summation in a recurrence relation

edited to reflect advice from the comments: While working on a generalization of a tiling problem, I generated a recurrence relation to describe the total number of possible tilings. The relation ...
0
votes
1answer
243 views

total number of different mixes

Patient Age Avg Visits / Year <1 year 7.5 1-4 years 3.0 5-14 years 1.8 15-24 years 1.7 25-44 years 2.6 45-64 years ...
1
vote
1answer
29 views

Possible arrangments Letters?

How many arrangements are possible of the letters in EZPZ I CAN DO IT, which has five vowels (A, E, I, I, O) and seven consonants (C, D, N, P, T, Z, Z). a) if there are no restrictions, b) if ...
0
votes
1answer
69 views

Count Integers satisfying the conditions

Given some constraints ,I need to find possible ways that these conditions are satisfied. I need to find four POSITIVE integers a,b,c,d such that ad-bc > 0 and also a+d=N for a given value of N. How ...
3
votes
2answers
122 views

A combinatorial question. Is this a known result, false, or open?

Let $X$ be a set of $n-1$ elements. Does there exist a family $S_1,S_2...S_n\in 2^X$ such that $$|S_i\cap S_j|\le 1$$ and $$|\overline S_i\cap \overline S_j|\le 1$$? That is, neither the sets ...
10
votes
2answers
238 views

Show that $\displaystyle\sum_{k=0}^n\binom{2n}{2k}^{\!2}-\sum_{k=0}^{n-1}\binom{2n}{2k+1}^{\!2}=(-1)^n\binom{2n}{n}$

How can I prove this $$ \sum_{k=0}^n\binom{2n}{2k}^2-\sum_{k=0}^{n-1}\binom{2n}{2k+1}^2=(-1)^n\binom{2n}{n}? $$ Maybe can we expand $$ f(x)=(1+x)^{2n}? $$ Thank you.
0
votes
2answers
39 views

A question in combinatorics

What is the possible number of ways in which 8 digit numbers can be made from 1,1,1,2,2,3,4,4 such that odd numbers do not occupy odd places ?
2
votes
1answer
33 views

Proving that if $n\times n$ Hadamard matrix exists, then 4 divides $n$

Im looking for an explanation of the following: a standard way to prove that, if there exists Hadamard matrix of dimension $n > 2$, then $4|n$, is to suppose that without loss of generality every ...
1
vote
2answers
39 views

Inequality with two binomial coefficients

I am having trouble seeing why $$ \binom{k}{2} + \binom{n - k}{2} \le \binom{1}{2} + \binom{n - 1}{2} = \binom{n - 1}{2} $$
1
vote
1answer
21 views

(Counting problem) very interesting Modular N algebraic eqs - for combinatorics experts

We have some attempt to numerically solve this math problem, which means that we like to count the number of independent solutions of this set of six of modular N algebraic equations: $$ (1) x_1 ...
8
votes
1answer
210 views

Bipartite graph: how many closed walk with given properties

Let be $G=(U,V,E)$ a bipartite graph where $U$ has $K$ possible vertices and $V$ has $N$ possible vertices. We focus on closed walks of length $2L$. Such walks can be described by the sequence of ...
1
vote
2answers
26 views

How do I calculate variance for sum of dice?

I'll post my work, but I'm not sure how to calculate variance. The question asks for the expected sum of 3 dice rolls and the variance. I think I got the expected sum. Any help would be awesome :) ...
28
votes
4answers
3k views

Probability for the length of the longest run in $n$ Bernoulli trials

Suppose a biased coin (probability of head being $p$) was flipped $n$ times. I would like to find the probability that the length of the longest run of heads, say $\ell_n$, exceeds a given number $m$, ...
0
votes
0answers
37 views

No of ways to reach out there

Suppose there are 12 stations between two places. A train starting at one of these two places stops in exactly four of these stations before reaching the other of these two places in such a way that ...
1
vote
1answer
26 views

What's wrong with this recursion of counting codes of length $n$ formed by $a$, $b$, and $c$ such that no three consecutive letters are distinct

I found the following problem in a combinatorics book and gave it a try. Let $B_n$ denote the set of codes of length $n$ formed by using the letters $a$, $b$, and $c$, none of which contains three ...
0
votes
1answer
41 views

Probability: put 20 distinct balls randomly in 12 urns

You put 20 distinct balls randomly into 12 urns. What is the probability of having 3 urns with 4 balls each and 4 urns with 2 balls each (the other 5 urns are left empty). For my sample space I have: ...
4
votes
1answer
61 views

How prove this can choose two postive integer numbers $a_{m},a_{k},$such $\frac{a_{m}+a_{k}}{3a_{p}}\notin N^{+},$

If $a_{1},a_{2},\cdots,a_{n}(a_{i}\neq a_{j}),n\ge 3$ are positive integers,show that: we can always choose two positive integers among them, $a_{m},a_{k},m,k\in\{1,2,\cdots,n\}$.such that ...
3
votes
1answer
52 views

How to evaluate this sum 2?

$\displaystyle\sum_{x+y+z=2014}xy^2z^3$ $\quad , x,y,z\in\mathbb{N}$ I think it maybe use combinatorial method.
2
votes
0answers
40 views

Uniqueness of projective plane of order 5

Is there a slick way to see the uniqueness of projective plane (equivalently, an affine plane) of order $5$?
0
votes
1answer
14 views

Simple question about choosing items from a box

Let's say I have a box of twelve balls and eight are blue and the rest red. When I choose seven balls at random, what is the probability of getting exactly two blue balls? I know it's a fraction ...
1
vote
1answer
38 views

Combinations and Probability Problems

I try this problem and I got $\binom{50}{20} * \binom{30}{20} * \binom{10}{10} = 1.416 * 10^{21}$ . I just want to make sure I have the right idea for this problem. In a medical experiment involving ...
1
vote
6answers
223 views

Prove that $\sum_{k=0}^n k^2{n \choose k} = {(n+n^2)2^{n-2}}$

Prove that: $$\sum_{k=0}^n k^2{n \choose k} = {(n+n^2)2^{n-2}}$$ i know that: $$\sum_{k=0}^n {n \choose k} = {2^n}$$ how to get the (n + n^2)?
1
vote
1answer
28 views

How many different possibilities for ordering distinct sorted elements

Quick question - How many ways do we have to place $m$ men and $w$ women in a queue, all with different heights, such that all men are placed in ascending order of heights between themselves and all ...
0
votes
1answer
55 views

Placing two queens on an $n \times m$ chessboard

I want to find the number of ways in which two queens can be placed on a chessboard so that they can attack each other. two queens can attack each other on a row, a column or on same diagonal just ...
2
votes
1answer
64 views

Possible shorter solution to this problem?

How many pairs of diagonals of a regular decagon are parallel? The answer is $45$, and is computed via: $$5\binom{4}{2} + 5 \binom{3}{2}$$ which comes as a result of fixing one vertex and ...
-2
votes
1answer
53 views

Finding $E[X^2]$ if $E[X] = \frac{\pi k}{4}$ [duplicate]

We try to approximate $\pi$ by choosing random points in a square and seeing if they lie within the inscribed circle. The probability that a point is in the circle is $\frac{\pi}{4}$. Suppose we ...
1
vote
1answer
751 views

Drawing 3 cards of same suit and 2 of a different suit

What is the probability of having 3 cards of the same suit and $2$ cards of the same suit (but a different suit than the first three) in a $5$ card hand from a standard $52$ card deck? What is the ...
1
vote
1answer
38 views

Probability and Combinations

In a family with 6 children, a. What is the probability of having three children of each sex? b. What is the probability of having four of one sex and two of the other sex? I know in this problem ...
1
vote
3answers
74 views

Proof that $ p $ | ${ p^n \choose k } $ for any prime $p$ and $ k < p^n$

I know how to prove the fact that $ p$ | ${ p \choose k } $ (when writing it as a fraction, $p$ cannot be divided by any of the $1\times2\times...\times k$ or $1\times2\times...\times(p-k)$ because ...
1
vote
2answers
54 views

Combinatorics help

Say there are infinite marbles of k colors and we have to pick n marbles out of them. The marbles must be picked up such that we have at least k different colored marbles. What are the possibility. ...
0
votes
2answers
195 views

Discrete Math - Combinatorics question about number of paths in an m x n lattice from one corner to another

Explain why the number of shortest paths in an $m \times n$ lattice from one corner to another is $${s \choose r}$$ where $$s = \text{total # of steps$\qquad$ and $\qquad r= $ total # of right ...
1
vote
3answers
95 views

How to prove that e^x is convex? [duplicate]

For convexity : $$e^{ta+(1-t)b} \leq t \cdot e^a+(1-t)e^b \Rightarrow e^{(a-b)^t} \leq te^{a-b} + 1 - t$$ Now I'm stuck on how to solve it further.
6
votes
6answers
352 views

Book on combinatorial identities

Do you know any good book that deals extensively with identities obtained using combinatorial and/or probabilistic arguments (e.g., by solving the same combinatorial or probability problem in two ...
1
vote
3answers
39 views

Sum of certain binomial coefficients

$$\sum_{k=0}^{m} \frac{(q+k)!}{k!q!}$$ I do not know how to even start this problem. Any general tips on these types of problems will also be welcomed.
2
votes
2answers
60 views

(Counting problem) very interesting Modular N algebraic eqs - for combinatorics-permutation experts

Experts in algebra please help: we would like to know the number of solutions for this set of six of modular N algebraic equations: $$ (1) \quad x_1 y_2 \equiv x_2 y_1 \pmod{N}\\ (2) \quad x_1 y_3 ...
2
votes
0answers
27 views

How do you find a minimum of a function with these tools?

Let's say I can define a group $G$ acting on a set of combinatorial objects $X$ and I have a function $f: X \to \Bbb{N}$ that I want to find a minimum of in $X$. Is there a polynomial time ...
0
votes
2answers
53 views

How do I prove this bijection?

The number of $n$-digit binary numbers with exactly $k$ $1$s equals the number of $k$-subsets of $[n]$. I think i'm on the right track, but I'm confused on how to write how it's onto and 1-1. This ...
1
vote
2answers
56 views

Who can not sit in middle if $A$ is not near $B$ and $C$ is beside $D$

Five people, $A,B,C,D,E$, are sitting in a row. $A$ is not near $B$. $C$ is beside $D$. Who can NOT sit in the middle? There are $5!=120$ combinations, that much I understood. But how do I answer the ...
3
votes
0answers
19 views

(Counting problem) more challenging Modular N algebraic eqs - for combinatorics-permutation experts

Experts in algebra please help - Part II after Part I: we would like to know the number of solutions for this set of six of modular N algebraic equations: $$ x_1 y_2 = x_2 y_1 \pmod N \qquad (1) \\ ...
3
votes
2answers
1k views

Number of 4-digit numerals with at most 2 different digits

How many 4 digit numbers are there which contain not more than two different digits? As usual, I will highlight my attempt: I can have 9 numbers using only 1 digit, e.g. $1111, 2222, \dots 9999$ = ...
4
votes
0answers
89 views

Combinatorial packages of N items [[How many distinct Boolean Expressions can be made using N variables]]

Using just the AND operator, the number of distinct packages that can be built from a set of size $n$, is simply $2^n$. If one adds the operators OR and XOR, how many packages can be built? That is, ...
1
vote
2answers
63 views

How find the what is the minimum number of operations required that the sums of any number of numbers in the list can never be $2014$

Question: Initially we have a list of numbers $1,2,3,\cdots,2013$.an operation is defined that taking two numbers $a, b$ out from the list, but add $a+b$ into it instead, what is the minimum ...
1
vote
1answer
20 views

For each positive integer n > 2 is there a “perfect” n-cubed n-cube?

Roland Sprague found the first "perfect" squared square. https://en.wikipedia.org/wiki/Squaring_the_square For each positive integer n > 3, is there an analogous "perfect" hypercubing of the hypercube ...
0
votes
2answers
36 views

Number of ways to sit 6 girls and 6 boys together with no two girls together.

As the title of the question explains: What I thought on the very first instant was that we will make them sit alternate hence the answer will be 2 * 6! * 6! But ...
3
votes
1answer
44 views

Ham-sandwich cut of red points and blue points in the plane.

For a finite set of points in the plane, each colored "red" or "blue", there is a line that simultaneously bisects the red points and bisects the blue points, that is, the number of red points on ...
0
votes
1answer
35 views

Give an example of a function from $X$ to $Y$

Give an example of a function from $X = \{1,2,3\}$ to $Y = \{0,1\}$. Let $F$ denote the set of all functions $f: X \rightarrow Y$. Show that $|F|=8$, by listing the members of $F$. My solution: a ...
2
votes
2answers
209 views

Combinatorics - multi-binomial special case 2 variable in n multiple parentheses and r summed locations

I came across the following combinatorial question and lost my way, wonder if you can assist ??? I think it might be a sub case of a multi-binomial theorem, maybe more related to set/multiset theorem. ...
0
votes
2answers
45 views

Finding coeffiicients

Given series expansion: $z^2/(1+z)^8$ Find coefficient of $z^{12}$. I know we can use geometric series to up solve $z^2/(1+z)^8$, by applying the series to $(1+z)^{-8}$. I don't know how to solve ...
2
votes
1answer
56 views

Algebraic Combinatorics

Let $K_{r,s}$ denote the complete bipartite graph, defined on $r + s$ vertices $\{v_1,v_2,...,v_r,w_1,...,w_s\}$, with an edge between $v_i$ and $w_j$ for $1 ≤ i ≤ r$ and $1 ≤ j ≤ s$. By ...
0
votes
2answers
461 views

soccer betting combinations for accumulators

I would like to bet on soccer games but I would like to place a bet on every combination possible. For example I bet on 10 different games, and each soccer match can go three ways, either a win, draw ...