Tagged Questions

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 (5)

1
vote
0answers
19 views

Show C is not 1-error correcting by using Slepian decoding

Let C $\subseteq$ $ \mathbb{Z}_2^5$be a linear code with generator matrix $$G=\begin{bmatrix}1 & 0 & 0 & 1 & 1\\ 0 & 1 & 0 & 1 & 1\\0 & 0 & 1 & 0 & ...
1
vote
1answer
39 views

Contructing elements of a partially ordered set of increasing integer sequences?

Let $\underline{d}= [\underline{d}_{1},\underline{d}_{2},...,\underline{d}_{n}]$ and $\overline{d}= [\overline{d}_{1},\overline{d}_{2},...,\overline{d}_{n}]$ where $\underline{d}_{i}\leq ...
4
votes
3answers
122 views

How many numbers $k$ of $200 \choose k$ are divisible by $3$? $k \in \{0,1,2,\cdots 200\}$

"How many of the numbers (200 Choose k), where k is an element of the set {0,1,2,3,4,....,200} are divisible by 3? " Here is my thinking: (200 Choose 0,1, and 2) are not multiples of 3 but every ...
1
vote
1answer
71 views

Counting problem, $p^2\ge q$

Let $A=\{1,2,...,n(n-1)\}$ with $n\geq2$ a natural number. Determine all pairs $(x,y)$ with elements from $A$ having the property $x^2\ge y$. How to approach this type of counting problems?
2
votes
1answer
154 views

Set/Subset number of combinations

I'm struggling on a counting problem, and I would like some help :) I'm rephrasing the problem to make it easy to understand ;) So, let's say I have a set of $n$ boxes. The $i$th box contains ...
3
votes
2answers
59 views

Which is the impossible voting in election?

Three candidates A, B, C are contesting an election. In an opinion poll fraction $a$ of voters prefer A to B, fraction $b$ prefer B to C and fraction $c$ prefer C to A. then which of the following ...
4
votes
2answers
190 views

How many arrangements are there with $n$ zeros($0$) and $m$ ones($1$) and $k$ runs of zeros

How many arrangements are there with $n$ zeros($0$) and $m$ ones($1$) and $k$ runs of zeros.A run is the same digit occurring consecutively 1 or more times. For example: $110010001110$ has 3 runs of ...
-1
votes
2answers
977 views

In how many different ways can the letters in the word APPOOPPAN be arranged? [closed]

In how many ways can the letters in APPOOPPAN be arranged ?
0
votes
3answers
142 views

Proving identity $ \binom{n}{k} = (-1)^k \binom{k-n-1}{k} $. How to interpret factorials and binomial coefficients with negative integers.

I at a loss on how to prove $$ \binom{n}{k} = (-1)^k \binom{k-n-1}{k} \tag{1} $$. I want to prove this because it appears to be a fundamental result, that is applied liberally in combinatorics ...
2
votes
1answer
66 views

Discrete math counting question help

100 students from each of the 3 schools form a line. For each student (except the 1st and the last), the two neighboring students must be from 2 schools different than his/her school. The 1st and last ...
12
votes
2answers
508 views

If 1 boy knows r girls and 1 girl knows r boys ,then number of boys=girls

Yet another question from BdMO 2013 Nationals: In a class,every boy knows $r$ number of girls and every girl knows $r$ number of boys.Show that there are equal number of boys and girls[Assume that ...
1
vote
2answers
128 views

Unimodality of q-binomial coefficients

The q-Pochhammer symbol $[n]_q!$ is defined as $$[n]_q! = \frac{(1-q^n)(1-q^{n-1})\cdots(1-q)}{(1-q)^n} = (1+q) (1+q+q^2) \cdots (1+q+\cdots+q^{n-1})$$ It can be easily shown that $[n]_q!$ (function ...
0
votes
1answer
85 views

How many numbers N satisfy N consecutive positive integers add to 2013?

How would you find how many numbers N there exist such that N consecutive positive integers add to 2013? (Assume that N=1 is a valid case whose solution is just 2013 itself). To clarify, this, when ...
-1
votes
1answer
67 views

Find the sums of the series (combinatorial series) [duplicate]

I would appreciate if somebody could help me with the following problem Q: Find ? $(n,k\in\mathbb{N},k\leq n)$ $$\binom{n}{0} +\binom{n}{1}+\binom{n}{2}+\ldots+\binom{n}{k}=\,?$$
0
votes
1answer
42 views

Is my reasoning for the number of five card hands with one card from each suit correct? Why or Why not?

How many five card hands have at least one card from each suit? I'm perplexed. I want to say that the answer is: $\binom{4}{1} \cdot \binom{13}{1} \cdot \binom{3}{1} \cdot \binom{13}{1} ...
2
votes
0answers
47 views

A certain sum of three variables

Let $0 < \gamma < 1.$ I have this sum $$ S(n) = \sum_{\stackrel{n = x_1+x_2+x_3, \ x_i > 0} { x_i \not = x_j}} \frac{1}{x_1^{\gamma} x_2^{\gamma} x_3^{\gamma}}. $$ I was curious to find ...
1
vote
1answer
49 views

Combinatorics / nCr - How do I set this up?

A Bag contains 5 red and 5 green gumballs. If you select 4 of them without looking, how many ways can you get exactly 3 red or exactly 2 green gumballs? I am unsure of how to start his. I know it has ...
1
vote
1answer
52 views

Number of possibilities in a partition problem

Given a set of n items, how many possibilities are there, to distribute these items in two sets with $\dfrac{n}{2}$ items, each? I came up with something like $\dfrac{n!}{\dfrac{n}{2}!}$ but the ...
4
votes
1answer
45 views

Combinatorics and upper bound

Consider the set $$ \{\lambda = \alpha _1^2 + \alpha _2^2 + \alpha _3 ^2 : \alpha _j \in \mathbb{Z}, \, j=1,2,3 \} $$ of real numbers. Assume I order this set so that $\lambda _1 \le \lambda _2 ...
2
votes
5answers
728 views

How many numbers must be selected from the set

How many numbers must be selected from the set {1, 3, 5, 7, 9, 11, 13, 15 } to guarantee that at least one pair of these numbers add up to 16, explain your answer?
0
votes
1answer
59 views

Find $E[XY]$ of joint hypergeometric by conditioning on $Y$

An urn contains $N = 30$ balls. There are $10$ balls of color X, and $8$ balls of color Y, and let random variables $X, Y$ denote the count of each, respectively. Also assume $n = 12$ balls are ...
-2
votes
2answers
151 views

permutations on number of ways boys and girls sit together

What is the difference between :- $5$ boys and $5$ girls need to sit in a row so that no two boys should sit together $5$ boys and $5$ girls should sit in a row alternatively ?
0
votes
1answer
74 views

Combination and permutation Discrete math problem

100 players from each of the 3 teams form a line. For each player (except first and last), the two neighboring players must be from 2 teams different than his team. The first and last player in the ...
1
vote
1answer
32 views

Joint distribution of RVs involving rolls of die

We roll a die until we get $4$ fives. Let $X$ be the number of rolls needed for the first $5$ and let $Y$ be the number of rolls needed to get the fourth five. What is the joint probability mass ...
4
votes
0answers
117 views

Card game probability

Suppose the following solitaire with a standard deck. I turn four cards visible on the board and on each turn, I remove those suits that appears more than once in the board. Then I fill the board such ...
-1
votes
1answer
23 views

Permutation combination questions?

An access pad has 7 buttons. An access code is a sequence of 2, 3, 4 buttons. How many access codes are possible if: buttons may be repeated buttons may not be repeated I need help getting this ...
1
vote
3answers
75 views

counting the number of paths from point $(0,0)$ to point $(n,m)$ on a recangular grid after N steps

Is there anyway to determine the total number of paths which start at the origin $(0,0)$ and finish at a point $(n,m)$ of a 2D rectangular grid after taking a total of N steps. On each step transition ...
0
votes
1answer
114 views

Combinations of a Multi-set with generating functions

Find the number of 5-combinations of the multi-set {4*a, 4*b, 4*c} using generating functions. Because I am finding combinations I know that I have to use ordinary generating functions and not ...
0
votes
4answers
93 views

How many four digit numbers are there?

Assume that 0 can't be a first digit. I got 9,000. Is that right? Follow up question: How many of those four digit numbers have no repeated digits?
1
vote
1answer
168 views

Uniqueness of doubly stochastic matrix descomposition

this is my first question in the site. Thanks in advance for all answers. It is well known that each bistochastic matrix can be represented as a convex combination of permutation matrices. I am ...
0
votes
1answer
39 views

Permutations and Combinations.

There are 4 red and 6 blue marbles in a bag, 3 are picked out at random, what is the probability that atleast one of them is red? My answer is 1/2 First I calculated the total number of ways that I ...
1
vote
1answer
37 views

Generating function for division of $n$ into smaller subsets.

I need to find the generating function for the number of ways of dividing $n$ into parts out of even numbers. The ways are only different if their parts are different, meaning that $2+1+2$ and $2+2+1$ ...
5
votes
3answers
124 views

How to minimize $|z_1 - z_2|^2 + |z_1 - z_4|^2 + |z_2 - z_3|^2 + |z_3 - z_4|^2$?

If $z_1,z_2,z_3,z_4 \in \mathbb{C}$ satisfy $z_1 + z_2 + z_3 + z_4 = 0$ and $|z_1|^2 + |z_2|^2 + |z_3|^2 + |z_4|^2 = 1$, then the least value of $|z_1 - z_2|^2 + |z_1 - z_4|^2 + |z_2 - z_3|^2 + ...
3
votes
1answer
121 views

Show that $\frac1{\sqrt{(n+\frac12) \pi}} \le\frac{1\cdot 3\cdot 5 … (2n-1)}{2\cdot 4\cdot 6 … (2n)} \le \frac1{\sqrt{n \pi}} $

Show that, if $n$ is a positive integer, $$\frac1{\sqrt{(n+\frac12) \pi}} \le\frac{1\cdot 3\cdot 5 ... (2n-1)}{2\cdot 4\cdot 6 ... (2n)} \le \frac1{\sqrt{n \pi}} . $$ This result is in a current ...
2
votes
1answer
31 views

Find the generating function for the sequence and use it to find a closed formula for $c_n$

Consider the equation $x_1+x_2+x_3+x_4sdj = n$ where $x_1,x_2,x_3,x_4 n\geq0$ are all integers. Suppose also that $x_2 \geq2$, $x_3$ is a multiple of 4, and $1 \leq{x_4}\geq3$. Let $c_n$ be the ...
0
votes
1answer
31 views

Solving a recurrence equation using generating functions

Let $a_0=0, a_1=2, a_2=5$. Use generating functions to solve recurrence equation $a_{n+3}= 5a_{n+2} - 7a_{n+1} + 3a_{n} + 2^n$ for $n \geq0$ I came up with $a_n = {(-1)^n + 2^{n+1}}/3$ but I know ...
3
votes
2answers
289 views

Pigeonhole Principle: birthdays on same day of week

How many people must be in a room so that at least 10 have a birthday on a Friday? edit: Assume that no two people share the same birthday I'm somewhat confused and see two different ways to ...
2
votes
1answer
548 views

Expressing a positive integer as a sum of positive integers

I am trying to find a way for the positive integers written as the sum of other positive integers.( expressed in terms of some functions) I searched a bit and I came across with Partitions But in my ...
0
votes
0answers
75 views

The set of distinct permutations of a list of integers under an inequality constraint at each index

Let k represent a set of integers such as: k = {5, 4, 4, 3, 3, 3, 2, 1, 1, 1, 1, 1, 0, 0, 0, 0} Also let K represent an ordered list of integers of the same length, such as: K = (10, 8, 7, 5, 4, 3, ...
2
votes
3answers
227 views

Use generating functions to solve recurrence equation.

Let $a_0=1, a_1=1$. Use generating functions to solve recurrence equation $a_{n+2}= a_{n+1} + 2a_n$ for $n \geq0$ I have no idea how to solve this, any help is appreciated.
1
vote
4answers
39 views

Permutation question

Leading zeros are not allowed 1) How many seven-digit numbers have no repeated digits? Would this one be $9*P(9,6)$ 2) How many seven-digit numbers with no repeated digits contain a 3 but not a 6? ...
1
vote
2answers
59 views

How to count “straight only” on poker

In a usual poker hand, I would like to calculate the probability that one has a straight. Without royal straights or flushes. I am comfortable with straight forward counting such as $nCr$ and $nPr$ ...
2
votes
1answer
57 views

Finding probability of earning points

A professor asks a true/false question with ten individual questions. Suppose the professor assigns grades of: $10$ points for each correct response, $0$ points for each absent response, and $-10$ for ...
0
votes
2answers
125 views

Probability regarding getting a full house

I am trying to calculate the probability of getting a full house on a standard 5-card deal. I am comfortable with how combinations, permutations and the fundamental principle of counting, but I am ...
0
votes
1answer
69 views

Inviting friends to dinner (combination/permutation)

The head of a large company has 9 close friends. a) In how many ways can he invite six of them to dinner? b) Repeat a) if two of his friends are divorced, hate each other, and cannot both be ...
1
vote
3answers
26 views
2
votes
2answers
356 views

Choosing a committee (combination problem)

A group of people is comprised of six from Nebraska, seven from Idaho, and eight from Louisiana. In how many ways can a committee of six be formed with two people from each state? ${^6C_2} \times ...
1
vote
1answer
43 views

$10$ apples, gives $3$ away. How many ways can she do this?

Jill has ten apples, and plans to give at most three of them to Jack. How many ways can she do this? Would this simply just be $C(10,3)$?
1
vote
1answer
113 views

Possibility of getting a 5 card hand all of the same suit

How many five-card hands dealt from a standard deck of $52$ playing cards are all of the same suit? If a random hand is dealt, what is the probability that it will have this property? Would the ...
1
vote
1answer
26 views

Four dogs and five cats race. In how many ways can this occur?

Four dogs and five cats enter a race. The cats are clearly superior; they place first, second, and third. In how many ways can this happen? My attempt: Since the cats come in the first three places ...